package com.demo.java.OD401_450.OD448;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【小明跳格子(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146327826
 */
public class OdMain {
    // 计算跳跃到最后格子能得到的最大得分
    public static int maxScore(int[] nums, int k) {
        int n = nums.length;

        // 如果只有一个格子，直接返回该格子的分数
        if (n == 1) {
            return nums[0];
        }

        // 创建一个数组来保存每个格子的最大得分
        int[] dp = new int[n];
        dp[0] = nums[0]; // 第一个格子的最大得分就是它自己的分数

        // 遍历每个格子
        for (int i = 1; i < n; i++) {
            int maxVal = Integer.MIN_VALUE; // 记录从当前格子可以跳到的最大得分
            // 计算从当前格子可以跳到前k个格子的最大得分
            for (int j = 1; j <= k; j++) {
                if (i - j >= 0) {
                    maxVal = Math.max(maxVal, dp[i - j]);
                }
            }
            // 更新当前格子的最大得分
            dp[i] = maxVal + nums[i];
        }

        // 返回最后一个格子的最大得分
        return dp[n - 1];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入
        int n = scanner.nextInt();  // 格子数量
        int[] scores = new int[n];  // 存储每个格子的分数
        for (int i = 0; i < n; i++) {
            scores[i] = scanner.nextInt();  // 读取每个格子的分数
        }
        int k = scanner.nextInt();  // 读取最多可跳跃的步数

        // 输出结果
        int result = maxScore(scores, k);
        System.out.println(result);  // 输出最终的最大分数

        scanner.close();
    }
}
